Jarvis and Friday

MiMCの毎回のstepsはlow-degree polynomialで表現することができSNARKs, STARKsのアプリケーションとして適している。

MiMC

100~150 constraints

https://eprint.iacr.org/2016/542.pdf : MPC-Friendly Symmetric Key Primitives

Rijndael

3000 constraints

https://gyazo.com/4cdbfe0257db1c4ea438433db37edea0

Jarvis

30~60 constaints

JARVIS

RijndealベースのSTARKフレンドリーなブロック暗号

AESのラインダール自体もSTARKフレンドリー

Rijndealは共通鍵暗号の標準暗号アルゴリズムAESに選定されたブロック暗号アルゴリズム

AESの規格ではブロック長は128ビット固定で鍵のビット長は128, 192, 256ビットの3種類。

RijndealはSubBytes, ShiftRows, MixColumns, AddRoundKeyの4つのラウンドから成るSPN構造。

128ビット（16バイト）ブロックずつを4×4 matrixとして見る。

https://gyazo.com/75fb5a5407eb6de656a02e877d241cf0

SubBytes

それぞれ1バイトごとに256文字の単一換字暗号処理を行う。つまり、256個の値を持っている換字表から1個の値を得るという処理をそれぞれに対して行う。

ShiftRows

4バイトのそれぞれの行を規則的に左にシフトしていく処理。シフトするバイト数は行によって異なる。

first rowは変えない。second rowは1バイトだけ左シフト。thirdは2つだけ、fourthは3つだけ。

MixColmuns

colmunの4バイトの値を行列ビット演算で別の4バイトの値に変換

AddRoundKey

それぞれのバイトに対してround keyとXORをとる。

Rijndealでは以上のラウンドを10〜14回繰り返す。

starkは固定長のfield elementsを使うので、RijndealをSTARK-fridnelyにするためにAESのelementの$ GF(2^8)^{16}の代わりに１つのfield elementとして、$ GF(2^{128})として扱う。

これにより復元化の関数をそれぞれのラウンドにおいて16回繰り返すのではなく、全てのstateに対して1回行えばOKになった。

affine layerをB(x), C(x)として定義。

jarvisのround function

https://gyazo.com/ef0bdbbf451b84eeae42f3ff8cf27f6f

FRIDAY

JARVIS AND FRIDAY: STARK-FRIENDLY CRYPTOGRAPHIC PRIMITIVES

MARVELlous: a STARK-Friendly Family of Cryptographic Primitives